#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // int strStr(string haystack, string needle)
    // {
    //     if (haystack.find(needle) != string::npos)
    //     {
    //         return haystack.find(needle);
    //     }
    //     else
    //     {
    //         return -1;
    //     }
    // }

    // int strStr(string haystack, string needle)
    // {
    //     int length1 = haystack.size();
    //     int length2 = needle.size();
    //     int start = 0;
    //     for (int i = 0; i < length1; i++)
    //     {
    //         if (haystack[i] == needle[start])
    //         {
    //             start++;
    //             if (start == length2)
    //             {
    //                 return i - length2 + 1;
    //             }
    //         }
    //         else
    //         {
    //             if (start != 0)
    //             {
    //                 i = i - start;
    //             }
    //             start = 0;
    //         }
    //     }
    //     return -1;
    // }

    void get_next(vector<int> &next, string &needle)
    {
        int j = 0;
        next[0] = 0;
        int length = needle.size();
        for (int i = 1; i < length; i++)
        {
            while (j > 0 && needle[i] != needle[j])
            {
                j = next[j - 1];
            }
            if (needle[i] == needle[j])
            {
                j++;
            }
            next[i] = j;
        }
    }

    int strStr(string haystack, string needle)
    {
        vector<int> next(needle.size());
        get_next(next, needle);
        int length = haystack.size();
        int length2 = needle.size();
        int j = 0;
        for (int i = 0; i < length; i++)
        {
            while (j > 0 && haystack[i] != needle[j])
            {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j])
            {
                j++;
            }
            if (j == length2)
            {
                return (i - length2 + 1);
            }
        }
        return -1;
    }
};

int main()
{
    string str1 = "aabaabaaf";
    string str2 = "aabaaf";
    Solution sol;
    cout << sol.strStr(str1, str2) << endl;
    return 0;
}